﻿/// <summary>
/// https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
/// </summary>
public class Solution
{
    private readonly Dictionary<char, IEnumerable<char>> numbersToAlphabets
         = new Dictionary<char, IEnumerable<char>>()
         {
             { '2', "abc" },
             { '3', "def" },
             { '4', "ghi" },
             { '5', "jkl" },
             { '6', "mno" },
             { '7', "pqrs" },
             { '8', "tuv" },
             { '9', "wxyz" }
         };

    private IEnumerable<IEnumerable<T>> Cartesian<T>(IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> tempProduct = new[] { Enumerable.Empty<T>() };
        return sequences.Aggregate(tempProduct, (accumulator, sequence) =>
                                        from accseq in accumulator
                                        from item in sequence
                                        select accseq.Concat(new[] { item }));
    }

    public IList<string> LetterCombinations(string digits)
    {
        var alphabets = from digit in digits
                        select this.numbersToAlphabets[digit];
        var result = this.Cartesian(alphabets).Select((item) => new string(item.ToArray())).ToList();
        _ = result.RemoveAll((s) => s == string.Empty);
        return result;
    }
}